package com.kitty.record.kittyalgorithm.audition;

import javax.swing.tree.TreeNode;

/**
 * 实现一个函数，检查二叉树是否平衡。
 * 在这个问题中，平衡树的定义如下：
 * 任意一个节点，其两棵子树的高度差不超过 1。
 * 示例 1: 给定二叉树 [3,9,20,null,null,15,7]
 *         3
 *        / \
 *       9  20
 *         /  \
 *        15  7
 * 返回 true 。
 * 示例 2: 给定二叉树 [1,2,2,3,3,null,null,4,4]
 *                 1
 *                / \
 *               2   2
 *              / \
 *             3   3
 *            / \
 *           4   4
 * 返回 false 。
 * @Author SHEN
 * @Date 2020/12/23
 */
public class LeetCode0404 {


    public boolean isBalanced(TreeNode root) {

        return height(root) >= 0;
    }


    public int height(TreeNode root){
        if(root == null){
            return 0;
        }

        int left = height(root.left);
        int right = height(root.right);

        if(left == -1 || right == -1 || Math.abs(right-left) > 1){
            return -1;
        }
        return Math.max(left,right) + 1;
    }


    private static class TreeNode {
        int val;
        TreeNode left;
        TreeNode right;

        TreeNode(int x) {
            val = x;
        }
    }
}
